{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #最强祝福力场"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: fieldOfGreatestBlessing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最强祝福力场"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "小扣在探索丛林的过程中，无意间发现了传说中“落寞的黄金之都”。而在这片建筑废墟的地带中，小扣使用探测仪监测到了存在某种带有「祝福」效果的力场。\n",
    "经过不断的勘测记录，小扣将所有力场的分布都记录了下来。`forceField[i] = [x,y,side]` 表示第 `i` 片力场将覆盖以坐标 `(x,y)` 为中心，边长为 `side` 的正方形区域。\n",
    "\n",
    "若任意一点的 **力场强度** 等于覆盖该点的力场数量，请求出在这片地带中 **力场强度** 最强处的 **力场强度**。\n",
    "\n",
    "**注意：** \n",
    "- 力场范围的边缘同样被力场覆盖。\n",
    "\n",
    "**示例 1：**\n",
    ">输入：\n",
    ">`forceField = [[0,0,1],[1,0,1]]`\n",
    ">\n",
    ">输出：`2`\n",
    ">\n",
    ">解释：如图所示，（0.5, 0) 处力场强度最强为 2， （0.5，-0.5）处力场强度同样是 2。\n",
    "![image.png](https://pic.leetcode.cn/1681805536-zGfghe-image.png){:width=400px}\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    ">输入：\n",
    ">`forceField = [[4,4,6],[7,5,3],[1,6,2],[5,6,3]]`\n",
    ">\n",
    ">输出：`3`\n",
    ">\n",
    ">解释：如下图所示，\n",
    ">`forceField[0]、forceField[1]、forceField[3]` 重叠的区域力场强度最大，返回 `3`\n",
    "![image.png](https://pic.leetcode.cn/1681805437-HQkyZS-image.png){:width=500px}\n",
    "\n",
    "\n",
    "\n",
    "**提示：**\n",
    "- `1 <= forceField.length <= 100`\n",
    "- `forceField[i].length == 3`\n",
    "- `0 <= forceField[i][0], forceField[i][1] <= 10^9`\n",
    "- `1 <= forceField[i][2] <= 10^9`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [xepqZ5](https://leetcode.cn/problems/xepqZ5/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [xepqZ5](https://leetcode.cn/problems/xepqZ5/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0,1],[1,0,1]]', '[[4,4,6],[7,5,3],[1,6,2],[5,6,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        x1, x2, y1, y2 = [], [], [], []\n",
    "        for x, y, d in forceField:\n",
    "            x1.append(x - d / 2)\n",
    "            x2.append(x + d / 2)\n",
    "            y1.append(y - d / 2)\n",
    "            y2.append(y + d / 2)\n",
    "\n",
    "        n = len(x1)\n",
    "        ans = 1\n",
    "        for x in x1 + x2:\n",
    "            for y in y1 + y2:\n",
    "                cnt = 0\n",
    "                for i in range(n):\n",
    "                    if x >= x1[i] and x <= x2[i] and y >= y1[i] and y <= y2[i]:\n",
    "                        cnt += 1\n",
    "                ans = max(ans, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        x1, x2, y1, y2 = [], [], [], []\n",
    "        for x, y, d in forceField:\n",
    "            x1.append(x - d / 2)\n",
    "            x2.append(x + d / 2)\n",
    "            y1.append(y - d / 2)\n",
    "            y2.append(y + d / 2)\n",
    "        n = len(x1)\n",
    "        ans = 1\n",
    "        for x in x1 + x2:\n",
    "            for y in y1 + y2:\n",
    "                cnt = 0\n",
    "                for i in range(n):\n",
    "                    if x >= x1[i] and y >= y1[i] and x <= x2[i] and y <= y2[i]:\n",
    "                        cnt += 1\n",
    "                ans = max(ans, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        x1, y1, x2, y2 = [], [], [], []\n",
    "        cnt = 0\n",
    "\n",
    "        for sq in forceField:\n",
    "            x1.append(sq[0] + sq[2] / 2)\n",
    "            y1.append(sq[1] + sq[2] / 2)\n",
    "            x2.append(sq[0] - sq[2] / 2)\n",
    "            y2.append(sq[1] - sq[2] / 2)\n",
    "\n",
    "        for x in x1 + x2:\n",
    "            for y in y1 + y2:\n",
    "                cur_cnt = 0\n",
    "                for i in range(len(x1)):\n",
    "                    if x >= x2[i] and x <= x1[i] and y >= y2[i] and y <= y1[i]:\n",
    "                        cur_cnt += 1\n",
    "                cnt = max(cnt, cur_cnt)\n",
    "        \n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        x1,x2,y1,y2=[],[],[],[]\n",
    "        for x,y,d in forceField:\n",
    "            x1.append(x-d/2)\n",
    "            x2.append(x+d/2) \n",
    "            y1.append(y-d/2) \n",
    "            y2.append(y+d/2) \n",
    "        cnt = 0\n",
    "        n = len(x1)\n",
    "        ans = 1\n",
    "        for x in x1+x2:\n",
    "            for y in y1+y2:\n",
    "                cnt = 0\n",
    "                for i in range(n):\n",
    "                    if x>=x1[i] and x<=x2[i] and y>=y1[i] and y<=y2[i]:\n",
    "                        cnt += 1\n",
    "                ans = max(cnt,ans)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        x1, x2, y1, y2 = [], [], [], []\n",
    "\n",
    "        for x, y, d in forceField:\n",
    "            x1.append(x - d / 2)\n",
    "            x2.append(x + d / 2)\n",
    "            y1.append(y - d / 2)\n",
    "            y2.append(y + d / 2)\n",
    "        n = len(x1)\n",
    "        ans = 1\n",
    "        for x in x1 + x2:\n",
    "            for y in y1 + y2:\n",
    "                 cnt = 0\n",
    "                 for i in range(n):\n",
    "                     if x >= x1[i] and y >= y1[i] and x <= x2[i] and y <= y2[i]:\n",
    "                        cnt += 1\n",
    "                 ans = max(ans,cnt)\n",
    "\n",
    "        return ans\n",
    "\n",
    "# 作者：Chap\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        x_left,x_right,y_up,y_down = [],[],[],[]\n",
    "        for i in forceField:\n",
    "            x_left.append(i[0]-i[2]/2)\n",
    "            x_right.append(i[0]+i[2]/2)\n",
    "            y_up.append(i[1]+i[2]/2)\n",
    "            y_down.append(i[1]-i[2]/2)\n",
    "        for x in x_left+x_right:\n",
    "            for y in y_up+y_down:\n",
    "                temp = 0\n",
    "                for n in range(len(forceField)):\n",
    "                    if x_left[n]<=x<=x_right[n] and y_down[n]<=y<=y_up[n]:\n",
    "                        temp += 1\n",
    "                ans = max(ans,temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        x1, x2, y1, y2 = [], [], [], []\n",
    "        for n, [x, y, d] in enumerate(forceField):\n",
    "            x1.append(x - d / 2)\n",
    "            x2.append(x + d / 2)\n",
    "            y1.append(y - d / 2)\n",
    "            y2.append(y + d / 2)\n",
    "        res = 1\n",
    "        for x in x1 + x2:\n",
    "            for y in y1 + y2:\n",
    "                cnt = 0\n",
    "                for i in range(n + 1):\n",
    "                    if x >= x1[i] and y >= y1[i] and x <= x2[i] and y <= y2[i]:\n",
    "                        cnt += 1\n",
    "                res = max(res, cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        n = len(forceField)\n",
    "        x1, x2, y1, y2 = [], [], [], []\n",
    "        for x, y, d in forceField:\n",
    "            x1.append(x - d / 2)\n",
    "            x2.append(x + d / 2)\n",
    "            y1.append(y - d / 2)\n",
    "            y2.append(y + d / 2)\n",
    "\n",
    "        ans = 0\n",
    "        for x in x1 + x2:\n",
    "            for y in y1 + y2:\n",
    "                cnt = 0\n",
    "                for i in range(n):\n",
    "                    if x1[i] <= x <= x2[i] and y1[i] <= y <= y2[i]:\n",
    "                        cnt += 1\n",
    "                ans = max(ans, cnt)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        x1,x2,y1,y2 = [],[],[],[]\n",
    "        for x,y,d in forceField:\n",
    "            x1.append(x - d / 2)\n",
    "            x2.append(x + d / 2)\n",
    "            y1.append(y - d / 2)\n",
    "            y2.append(y + d / 2)\n",
    "        n = len(x1)\n",
    "        ans = 1\n",
    "        for x in x1 + x2:\n",
    "            for y in y1 + y2:\n",
    "                 cnt = 0\n",
    "                 for i in range(n):\n",
    "                     if x >= x1[i] and y >= y1[i] and x <= x2[i] and y <= y2[i]:\n",
    "                        cnt += 1\n",
    "                 ans = max(ans,cnt)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        s = []\n",
    "        for x,y,side in forceField:\n",
    "            x2 = x<<1\n",
    "            y2 = y<<1\n",
    "            s.append((x2-side, y2-side, x2+side, y2+side))\n",
    "        \n",
    "        s.sort()\n",
    "\n",
    "        heap = []\n",
    "        ans = 0\n",
    "        for x1,y1,x2,y2 in s:\n",
    "            while heap and heap[0][0] < x1:\n",
    "                heapq.heappop(heap)\n",
    "            heapq.heappush(heap, (x2,y1,y2))\n",
    "            arr = []\n",
    "            for _, i1,i2 in heap:\n",
    "                arr.append((i1,1))\n",
    "                arr.append((i2+1,-1))\n",
    "            arr.sort()\n",
    "            sm = 0\n",
    "            for _, diff in arr:\n",
    "                sm += diff\n",
    "                if sm > ans:\n",
    "                    ans = sm\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, s: List[List[int]]) -> int:\n",
    "        \n",
    "        # 重叠最多的矩形的点肯定在forceField中\n",
    "        sx,sy=set(),set()\n",
    "        for x,y,d in s:\n",
    "            sx.add(x-d/2)\n",
    "            sy.add(y-d/2)\n",
    "        \n",
    "        res=0\n",
    "        for x in sx:\n",
    "            for y in sy:\n",
    "                cnt=0\n",
    "                for x1,y1,d in s:\n",
    "                    if x1-d/2<=x<=x1+d/2 and y1-d/2<=y<=y1+d/2:\n",
    "                        cnt+=1\n",
    "                if cnt>res:\n",
    "                    res=cnt\n",
    "                #res=max(res,cnt)\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        # 1. 统计所有左下和右上坐标\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "        for i, j, side in forceField:\n",
    "            x_set.add(2 * i - side)\n",
    "            x_set.add(2 * i + side)\n",
    "            y_set.add(2 * j - side)\n",
    "            y_set.add(2 * j + side)\n",
    "\n",
    "        # 2. 离散化\n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "        n, m = len(xs), len(ys)\n",
    "\n",
    "        # 3. 二维差分：快速地把一个矩形范围内的数都 +1\n",
    "        diff = [[0] * (m + 2) for _ in range(n + 2)]\n",
    "        for i, j, side in forceField:\n",
    "            r1 = bisect_left(xs, 2 * i - side)\n",
    "            r2 = bisect_left(xs, 2 * i + side)\n",
    "            c1 = bisect_left(ys, 2 * j - side)\n",
    "            c2 = bisect_left(ys, 2 * j + side)\n",
    "            # 将区域 r1<=r<=r2 && c1<=c<=c2 上的数都加上 x\n",
    "            # 多 +1 是为了方便求后面用二维前缀和复原\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 4. 直接在 diff 上复原（二维前缀和），计算最大值\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "                ans = max(ans, diff[i][j])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        def add(diff, r1, c1, r2, c2):\n",
    "            diff[1+r1][1+c1] += 1\n",
    "            # print('1', 1+r1, 1+c1)\n",
    "            diff[1+r1][2+c2] += -1\n",
    "            # print('2', 1+r1, 2+c2)\n",
    "            diff[2+r2][1+c1] += -1\n",
    "            # print('3', r2+2, 1+c1)\n",
    "            diff[2+r2][2+c2] += 1\n",
    "            # print('4', r2+2, 2+c2)\n",
    "            # print(diff)\n",
    "            \n",
    "        \n",
    "        def build(diff):\n",
    "            for i in range(1, len(diff)-1):\n",
    "                for j in range(1, len(diff[0])-1):\n",
    "                    diff[i][j] += diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1]\n",
    "\n",
    "        def froce_sort(xs):\n",
    "            xs.sort()\n",
    "            x_size = 0\n",
    "            for i in range(1, len(xs)):\n",
    "                if xs[x_size]!=xs[i]:\n",
    "                    x_size += 1\n",
    "                    xs[x_size] = xs[i]\n",
    "            return x_size+1\n",
    "\n",
    "        def rank(xs, x, x_size):\n",
    "            l = 0\n",
    "            r = x_size-1\n",
    "            while l<r:\n",
    "                mid = l+(r-l)//2\n",
    "                if xs[mid]<x:\n",
    "                    l = mid+1\n",
    "                elif xs[mid]>x:\n",
    "                    r = mid-1\n",
    "                else:\n",
    "                    return mid\n",
    "            return l\n",
    "\n",
    "        xs = []\n",
    "        ys = []\n",
    "        for i in range(len(forceField)):\n",
    "            xs.append(2*forceField[i][0]-forceField[i][2])\n",
    "            xs.append(2*forceField[i][0]+forceField[i][2])\n",
    "            ys.append(2*forceField[i][1]-forceField[i][2])\n",
    "            ys.append(2*forceField[i][1]+forceField[i][2])\n",
    "        x_size = froce_sort(xs)\n",
    "        y_size = froce_sort(ys)\n",
    "        # print(xs, x_size)\n",
    "        # print(ys, y_size)\n",
    "        diff = [[0 for i in range(y_size+2)] for j in range(x_size+2)]\n",
    "        for i in range(len(forceField)):\n",
    "            x = forceField[i][0]\n",
    "            y = forceField[i][1]\n",
    "            r = forceField[i][2]\n",
    "            xl = 2*x-r\n",
    "            xr = 2*x+r\n",
    "            yd = 2*y-r\n",
    "            yt = 2*y+r\n",
    "            # print(rank(ys, yt, y_size), rank(xs, xl, x_size), rank(ys, yd, y_size), rank(xs, xr, x_size))\n",
    "            add(diff, rank(xs, xl, x_size), rank(ys, yd, y_size), rank(xs, xr, x_size), rank(ys, yt, y_size))\n",
    "        build(diff)\n",
    "        # print(diff)\n",
    "        return max(map(max, diff))\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        def add(diff, r1, c1, r2, c2):\n",
    "            diff[1+r1][1+c1] += 1\n",
    "            # print('1', 1+r1, 1+c1)\n",
    "            diff[1+r1][2+c2] += -1\n",
    "            # print('2', 1+r1, 2+c2)\n",
    "            diff[2+r2][1+c1] += -1\n",
    "            # print('3', r2+2, 1+c1)\n",
    "            diff[2+r2][2+c2] += 1\n",
    "            # print('4', r2+2, 2+c2)\n",
    "            # print(diff)\n",
    "            \n",
    "        \n",
    "        def build(diff):\n",
    "            for i in range(1, len(diff)-1):\n",
    "                for j in range(1, len(diff[0])-1):\n",
    "                    diff[i][j] += diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1]\n",
    "\n",
    "        def froce_sort(xs):\n",
    "            xs.sort()\n",
    "            x_size = 0\n",
    "            for i in range(1, len(xs)):\n",
    "                if xs[x_size]!=xs[i]:\n",
    "                    x_size += 1\n",
    "                    xs[x_size] = xs[i]\n",
    "            return x_size+1\n",
    "\n",
    "        def rank(xs, x, x_size):\n",
    "            l = 0\n",
    "            r = x_size-1\n",
    "            while l<r:\n",
    "                mid = l+(r-l)//2\n",
    "                if xs[mid]<x:\n",
    "                    l = mid+1\n",
    "                elif xs[mid]>x:\n",
    "                    r = mid-1\n",
    "                else:\n",
    "                    return mid\n",
    "            return l\n",
    "\n",
    "        xs = []\n",
    "        ys = []\n",
    "        for i in range(len(forceField)):\n",
    "            xs.append(2*forceField[i][0]-forceField[i][2])\n",
    "            xs.append(2*forceField[i][0]+forceField[i][2])\n",
    "            ys.append(2*forceField[i][1]-forceField[i][2])\n",
    "            ys.append(2*forceField[i][1]+forceField[i][2])\n",
    "        x_size = froce_sort(xs)\n",
    "        y_size = froce_sort(ys)\n",
    "        # print(xs, x_size)\n",
    "        # print(ys, y_size)\n",
    "        diff = [[0 for i in range(y_size+2)] for j in range(x_size+2)]\n",
    "        for i in range(len(forceField)):\n",
    "            x = forceField[i][0]\n",
    "            y = forceField[i][1]\n",
    "            r = forceField[i][2]\n",
    "            xl = 2*x-r\n",
    "            xr = 2*x+r\n",
    "            yd = 2*y-r\n",
    "            yt = 2*y+r\n",
    "            # print(rank(ys, yt, y_size), rank(xs, xl, x_size), rank(ys, yd, y_size), rank(xs, xr, x_size))\n",
    "            add(diff, rank(xs, xl, x_size), rank(ys, yd, y_size), rank(xs, xr, x_size), rank(ys, yt, y_size))\n",
    "        build(diff)\n",
    "        # print(diff)\n",
    "        return max(map(max, diff))\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "        for i, j, side in forceField:\n",
    "            x_set.add(2 * i - side)\n",
    "            x_set.add(2 * i + side)\n",
    "            y_set.add(2 * j - side)\n",
    "            y_set.add(2 * j + side)\n",
    "        \n",
    "        # 离散化\n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "        m, n = len(xs), len(ys)\n",
    "\n",
    "        # 二维差分\n",
    "        diff = [[0] * (n+2) for _ in range(m+2)]\n",
    "        for i, j, side in forceField:\n",
    "            r1 = bisect_left(xs, 2 * i - side)\n",
    "            r2 = bisect_left(xs, 2 * i + side)\n",
    "            c1 = bisect_left(ys, 2 * j - side)\n",
    "            c2 = bisect_left(ys, 2 * j + side)\n",
    "\n",
    "            diff[r1+1][c1+1] += 1\n",
    "            diff[r1+1][c2+2] -= 1\n",
    "            diff[r2+2][c1+1] -= 1\n",
    "            diff[r2+2][c2+2] += 1\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n +1):\n",
    "                diff[i][j] += diff[i][j-1] + diff[i-1][j] - diff[i-1][j-1]\n",
    "                res = max(res, diff[i][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "\n",
    "        for i , j , side in forceField:\n",
    "            x_set.add(2 * i - side)\n",
    "            x_set.add(2 * i + side)\n",
    "            y_set.add(2 * j - side)\n",
    "            y_set.add(2 * j + side)         \n",
    "        \n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "\n",
    "        n , m = len(xs) ,len(ys)\n",
    "\n",
    "        diff = [[0] *  (m + 2) for _ in range(n + 2)]\n",
    "        for i, j , side in forceField:\n",
    "            r1 = bisect_left(xs, 2 * i - side)\n",
    "            r2 = bisect_left(xs, 2 * i + side)\n",
    "            c1 = bisect_left(ys, 2 * j - side)\n",
    "            c2 = bisect_left(ys, 2 * j + side)\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(1 , n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                diff[i][j] += diff[i][j-1] + diff[i-1][j] - diff[i-1][j-1]\n",
    "                ans = max(ans, diff[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "\n",
    "        # 1. 统计角点坐标，乘2避免非整数\n",
    "        for x, y, side in forceField:\n",
    "            x_set.add(2 * x - side)\n",
    "            x_set.add(2 * x + side)\n",
    "            y_set.add(2 * y - side)\n",
    "            y_set.add(2 * y + side)\n",
    "\n",
    "        # 2. 离散化，将角点坐标转化为序列下标\n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "        # n,m为转化后的数组大小\n",
    "        n, m = len(xs), len(ys)\n",
    "\n",
    "        # 3. 二维差分\n",
    "        # 维度+2是为了后续计算方便（差分时需要对下标+1，+2）,以(x, y)形式储存应为n+2行m+2列\n",
    "        diff = [[0] * (m + 2) for _ in range(n + 2)]\n",
    "        '''\n",
    "            二维差分：\n",
    "            使用左下角点的右上范围力场+1，\n",
    "            左上角点的右上范围力场-1，\n",
    "            右下角点的右上范围力场-1，\n",
    "            右上加点的右上范围力场+1的方式\n",
    "            标记该矩形力场的范围，并以角点下标+1的形式方便后续二维前缀和操作\n",
    "        '''\n",
    "        for x, y, side in forceField:\n",
    "            # 求下标\n",
    "            r1 = bisect_left(xs, 2 * x - side)\n",
    "            r2 = bisect_left(xs, 2 * x + side)\n",
    "            c1 = bisect_left(ys, 2 * y - side)\n",
    "            c2 = bisect_left(ys, 2 * y + side)\n",
    "            # 下标+1，防止后续二维前缀和操作中下标超出范围（-1）\n",
    "            # x >= xs[r1] y >= ys[c1]范围+1\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            # x >= xs[r1] y > ys[c2]范围-1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            # x > xs[r2] y >= ys[c1]范围-1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            # x > xs[r2] y > ys[c2]范围+1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 4. 直接在diff上求二维前缀和，然后返回最大力场\n",
    "        ''' \n",
    "            当前diff[i][j]表示从(xs[i-1],ys[j-1])亦可记作(x_i,y_j)点开始右上范围内增加/减少的力场\n",
    "            (x_i, y_j)真实的力场应为：角点x轴下标 r <= r_i, y轴下标c <= c_j的增加/减少力场的和\n",
    "            记force[x][y]为坐标(x, y)的力场（显然力场最大的位置在角点）\n",
    "            force[x_0][y_0] = diff[x_0][y_0] = 0\n",
    "            force[x_1][y_0] = diff[x_0][y_0] + diff[x_1][y_0] = diff[x_1][y_0] + force[x_0][y_0] = 0\n",
    "            force[x_0][y_1] = diff[x_0][y_0] + diff[x_0][y_1] = diff[x_0][y_1] + force[x_0][y_0] = 0\n",
    "            force[x_1][y_1] = diff[x_0][y_0] + diff[x_0][y_1] + diff[x_1][y_0] + diff[x_1][y_1]\n",
    "                            = diff[x_1][y_1] + force[x_1][y_0] + force[x_0][y_1] -force[x_0][y_0]\n",
    "            通过数学归纳易证对i >= 1, j >= 1有：\n",
    "            force[x_i][y_j] = diff[x_i][y_j] + force[x_{i-1}][y_j] + force[x_i][y_{j-1}] - force[x_{i-1}][y_{j-1}]\n",
    "        '''\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]\n",
    "                if ans < diff[i][j]:\n",
    "                    ans = diff[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        # 1. 统计所有左下和右上坐标\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "        for i, j, side in forceField:\n",
    "            x_set.add(2 * i - side)\n",
    "            x_set.add(2 * i + side)\n",
    "            y_set.add(2 * j - side)\n",
    "            y_set.add(2 * j + side)\n",
    "\n",
    "        # 2. 离散化\n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "        n, m = len(xs), len(ys)\n",
    "\n",
    "        # 3. 二维差分：快速地把一个矩形范围内的数都 +1\n",
    "        diff = [[0] * (m + 2) for _ in range(n + 2)]\n",
    "        for i, j, side in forceField:\n",
    "            r1 = bisect_left(xs, 2 * i - side)\n",
    "            r2 = bisect_left(xs, 2 * i + side)\n",
    "            c1 = bisect_left(ys, 2 * j - side)\n",
    "            c2 = bisect_left(ys, 2 * j + side)\n",
    "            # 将区域 r1<=r<=r2 && c1<=c<=c2 上的数都加上 x\n",
    "            # 多 +1 是为了方便求后面用二维前缀和复原\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 4. 直接在 diff 上复原（二维前缀和），计算最大值\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "                ans = max(ans, diff[i][j])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        # 1. 统计所有左下和右上坐标\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "        for i, j, side in forceField:\n",
    "            x_set.add(2 * i - side)\n",
    "            x_set.add(2 * i + side)\n",
    "            y_set.add(2 * j - side)\n",
    "            y_set.add(2 * j + side)\n",
    "\n",
    "        # 2. 离散化\n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "        n, m = len(xs), len(ys)\n",
    "\n",
    "        # 3. 二维差分：快速地把一个矩形范围内的数都 +1\n",
    "        diff = [[0] * (m + 2) for _ in range(n + 2)]\n",
    "        for i, j, side in forceField:\n",
    "            r1 = bisect_left(xs, 2 * i - side)\n",
    "            r2 = bisect_left(xs, 2 * i + side)\n",
    "            c1 = bisect_left(ys, 2 * j - side)\n",
    "            c2 = bisect_left(ys, 2 * j + side)\n",
    "            # 将区域 r1<=r<=r2 && c1<=c<=c2 上的数都加上 x\n",
    "            # 多 +1 是为了方便求后面用二维前缀和复原\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 4. 直接在 diff 上复原（二维前缀和），计算最大值\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "                ans = max(ans, diff[i][j])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        # 1. 统计所有左下和右上坐标\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "        for i, j, side in forceField:\n",
    "            x_set.add(2 * i - side)\n",
    "            x_set.add(2 * i + side)\n",
    "            y_set.add(2 * j - side)\n",
    "            y_set.add(2 * j + side)\n",
    "\n",
    "        # 2. 离散化\n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "        n, m = len(xs), len(ys)\n",
    "\n",
    "        # 3. 二维差分：快速地把一个矩形范围内的数都 +1\n",
    "        diff = [[0] * (m + 2) for _ in range(n + 2)]\n",
    "        for i, j, side in forceField:\n",
    "            r1 = bisect_left(xs, 2 * i - side)\n",
    "            r2 = bisect_left(xs, 2 * i + side)\n",
    "            c1 = bisect_left(ys, 2 * j - side)\n",
    "            c2 = bisect_left(ys, 2 * j + side)\n",
    "            # 将区域 r1<=r<=r2 && c1<=c<=c2 上的数都加上 x\n",
    "            # 多 +1 是为了方便求后面用二维前缀和复原\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 4. 直接在 diff 上复原（二维前缀和），计算最大值\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "                ans = max(ans, diff[i][j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        xset=set()\n",
    "        yset=set()\n",
    "        for x,y,side in forceField:\n",
    "            xset.add(2*x-side)\n",
    "            xset.add(2*x+side)\n",
    "            yset.add(2*y-side)\n",
    "            yset.add(2*y+side)\n",
    "        xs=sorted(xset)\n",
    "        ys=sorted(yset)\n",
    "        m,n=len(xs),len(ys)\n",
    "        diff=[[0]*(n+2) for _ in range(m+2)]\n",
    "        for x,y,side in forceField:\n",
    "            r1=bisect_left(xs,2*x-side)\n",
    "            r2=bisect_left(xs,2*x+side)\n",
    "            c1=bisect_left(ys,2*y-side)\n",
    "            c2=bisect_left(ys,2*y+side)\n",
    "            diff[r1+1][c1+1]+=1\n",
    "            diff[r1+1][c2+2]-=1\n",
    "            diff[r2+2][c1+1]-=1\n",
    "            diff[r2+2][c2+2]+=1\n",
    "        ans=0\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                diff[i][j]+=diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1]\n",
    "                ans=max(ans,diff[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "        for x, y, l in forceField:\n",
    "            x_set.add(2*x - l)\n",
    "            x_set.add(2*x + l)\n",
    "            y_set.add(2*y - l)\n",
    "            y_set.add(2*y + l)\n",
    "\n",
    "        #离散化，映射值为对应的索引\n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "\n",
    "        #离散化后大小\n",
    "        m, n = len(xs), len(ys)\n",
    "        #构造差分矩阵(m+2)*(n+2)\n",
    "        diff = [[0]*(n + 2) for _ in range(m + 2)]\n",
    "        #遍历并开始差分\n",
    "        for x, y, l in forceField:\n",
    "            #对于原始坐标，计算其差分后的对应坐标\n",
    "            r1n = bisect_left(xs, 2*x - l)\n",
    "            r2n = bisect_left(xs, 2*x + l)\n",
    "            c1n = bisect_left(ys, 2*y - l)\n",
    "            c2n = bisect_left(ys, 2*y + l)\n",
    "\n",
    "            #开始差分\n",
    "            diff[r1n + 1][c1n + 1] += 1\n",
    "            diff[r1n + 1][c2n + 2] -= 1\n",
    "            diff[r2n + 2][c1n + 1] -= 1\n",
    "            diff[r2n + 2][c2n + 2] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]\n",
    "                ans = max(ans, diff[i][j])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        # 1. 统计所有左下和右上坐标\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "        for i, j, side in forceField:\n",
    "            x_set.add(2 * i - side)\n",
    "            x_set.add(2 * i + side)\n",
    "            y_set.add(2 * j - side)\n",
    "            y_set.add(2 * j + side)\n",
    "\n",
    "        # 2. 离散化\n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "        n, m = len(xs), len(ys)\n",
    "\n",
    "        # 3. 二维差分：快速地把一个矩形范围内的数都 +1\n",
    "        diff = [[0] * (m + 2) for _ in range(n + 2)]\n",
    "        for i, j, side in forceField:\n",
    "            r1 = bisect_left(xs, 2 * i - side)\n",
    "            r2 = bisect_left(xs, 2 * i + side)\n",
    "            c1 = bisect_left(ys, 2 * j - side)\n",
    "            c2 = bisect_left(ys, 2 * j + side)\n",
    "            # 将区域 r1<=r<=r2 && c1<=c<=c2 上的数都加上 x\n",
    "            # 多 +1 是为了方便求后面用二维前缀和复原\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 4. 直接在 diff 上复原（二维前缀和），计算最大值\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "                ans = max(ans, diff[i][j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        def sort1(nums):\n",
    "            nums.sort()\n",
    "            size = 1\n",
    "            for i in range(1,len(nums)):\n",
    "                if nums[i] != nums[size-1]:\n",
    "                    nums[size] = nums[i]\n",
    "                    size += 1\n",
    "            return size\n",
    "        def add(diff,a,b,c,d):\n",
    "            diff[a][b]+=1\n",
    "            diff[c+1][d+1]+=1\n",
    "            diff[c+1][b]-=1\n",
    "            diff[a][d+1]-=1\n",
    "        def rank(nums,v,size):\n",
    "            l,r = 0,size-1\n",
    "            ans = 0\n",
    "            while l<=r:\n",
    "                m = (l+r)//2\n",
    "                if nums[m]>=v:\n",
    "                    ans = m\n",
    "                    r = m-1\n",
    "                else:\n",
    "                    l=m+1\n",
    "            return ans+1\n",
    "\n",
    "\n",
    "        n = len(forceField)\n",
    "        xs = [0]*(n<<1)\n",
    "        ys = [0]*(n<<1)\n",
    "        k = 0\n",
    "        p = 0\n",
    "        for i in range(n):          \n",
    "            x = forceField[i][0]\n",
    "            y = forceField[i][1]\n",
    "            r = forceField[i][2]\n",
    "            xs[k] = (x<<1)-r\n",
    "            k += 1\n",
    "            xs[k] = (x<<1)+r\n",
    "            k += 1\n",
    "            ys[p] = (y<<1)-r\n",
    "            p += 1\n",
    "            ys[p] = (y<<1)+r\n",
    "            p += 1\n",
    "        sizex = sort1(xs)\n",
    "        sizey = sort1(ys)\n",
    "        diff = [[0]*(sizey+2) for _ in range(sizex+2)]\n",
    "        for i in range(n):\n",
    "            x = forceField[i][0]\n",
    "            y = forceField[i][1]\n",
    "            r = forceField[i][2]\n",
    "            a = rank(xs,(x<<1)-r,sizex)\n",
    "            b = rank(ys,(y<<1)-r,sizey)\n",
    "            c = rank(xs,(x<<1)+r,sizex)\n",
    "            d = rank(ys,(y<<1)+r,sizey)\n",
    "            add(diff,a,b,c,d)\n",
    "        ans = 0\n",
    "        for i in range(1,len(diff)):\n",
    "            for j in range(1,len(diff[0])):\n",
    "                diff[i][j] += diff[i][j-1]+diff[i-1][j]-diff[i-1][j-1]\n",
    "                ans = max(ans,diff[i][j])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        xs,ys = [],[]\n",
    "        for x,y,side in forceField:\n",
    "            xs.append(x*2-side)\n",
    "            xs.append(x*2+side)\n",
    "            ys.append(y*2-side)\n",
    "            ys.append(y*2+side)\n",
    "\n",
    "        xs.sort()\n",
    "        ys.sort()\n",
    "\n",
    "        m,n = len(xs), len(ys)\n",
    "        dp = [[0]*(n+2) for _ in range(m+2)]\n",
    "        for x,y,side in forceField:\n",
    "            i1 = bisect.bisect_right(xs, 2*x-side)\n",
    "            i2 = bisect.bisect_right(xs, 2*x+side)\n",
    "            j1 = bisect.bisect_right(ys, 2*y-side)\n",
    "            j2 = bisect.bisect_right(ys, 2*y+side)\n",
    "            dp[i1][j1] += 1\n",
    "            dp[i2+1][j1] -= 1\n",
    "            dp[i1][j2+1] -= 1\n",
    "            dp[i2+1][j2+1] += 1\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1,m+2):\n",
    "            for j in range(1,n+2):\n",
    "                dp[i][j] += dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]\n",
    "                if dp[i][j] > ans:\n",
    "                    ans = dp[i][j]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "        for i, j, side in forceField:\n",
    "            x_set.add(i - 0.5*side)\n",
    "            x_set.add(i + 0.5*side)\n",
    "            y_set.add(j - 0.5*side)\n",
    "            y_set.add(j + 0.5*side)\n",
    "\n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "        n, m = len(xs), len(ys)\n",
    "\n",
    "        diff = [[0] * (m + 2) for _ in range(n + 2)]\n",
    "        for i, j, side in forceField:\n",
    "            r1 = bisect_left(xs, i - 0.5*side) #左下水平index\n",
    "            r2 = bisect_left(xs, i + 0.5*side) #右上水平index\n",
    "            c1 = bisect_left(ys, j - 0.5*side) #左下垂直index\n",
    "            c2 = bisect_left(ys, j + 0.5*side) #右上垂直index\n",
    "\n",
    "            diff[r1][c1] += 1\n",
    "            diff[r1][c2+1] -= 1\n",
    "            diff[r2+1][c1] -= 1\n",
    "            diff[r2+1][c2+1] += 1\n",
    "\n",
    "        def helper(x:int,y:int)->int:\n",
    "            if x<0 or y<0:\n",
    "                return 0\n",
    "            else:\n",
    "                return diff[x][y]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                diff[i][j] += helper(i,j - 1) + helper(i-1,j) - helper(i-1,j-1)\n",
    "                ans = max(ans, diff[i][j])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        # 1. 统计所有左下和右上坐标\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "        for i, j, side in forceField:\n",
    "            x_set.add(2 * i - side)\n",
    "            x_set.add(2 * i + side)\n",
    "            y_set.add(2 * j - side)\n",
    "            y_set.add(2 * j + side)\n",
    "\n",
    "        # 2. 离散化\n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "        n, m = len(xs), len(ys)\n",
    "\n",
    "        # 3. 二维差分：快速地把一个矩形范围内的数都 +1\n",
    "        diff = [[0] * (m + 2) for _ in range(n + 2)]\n",
    "        for i, j, side in forceField:\n",
    "            r1 = bisect_left(xs, 2 * i - side)\n",
    "            r2 = bisect_left(xs, 2 * i + side)\n",
    "            c1 = bisect_left(ys, 2 * j - side)\n",
    "            c2 = bisect_left(ys, 2 * j + side)\n",
    "            # 将区域 r1<=r<=r2 && c1<=c<=c2 上的数都加上 x\n",
    "            # 多 +1 是为了方便求后面用二维前缀和复原\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 4. 直接在 diff 上复原（二维前缀和），计算最大值\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "                ans = max(ans, diff[i][j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        # 1. 统计所有左下和右上坐标\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "        for i, j, side in forceField:\n",
    "            x_set.add(2 * i - side)\n",
    "            x_set.add(2 * i + side)\n",
    "            y_set.add(2 * j - side)\n",
    "            y_set.add(2 * j + side)\n",
    "\n",
    "        # 2. 离散化\n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "        n, m = len(xs), len(ys)\n",
    "\n",
    "        # 3. 二维差分：快速地把一个矩形范围内的数都 +1\n",
    "        diff = [[0] * (m + 2) for _ in range(n + 2)]\n",
    "        for i, j, side in forceField:\n",
    "            r1 = bisect_left(xs, 2 * i - side)\n",
    "            r2 = bisect_left(xs, 2 * i + side)\n",
    "            c1 = bisect_left(ys, 2 * j - side)\n",
    "            c2 = bisect_left(ys, 2 * j + side)\n",
    "            # 将区域 r1<=r<=r2 && c1<=c<=c2 上的数都加上 x\n",
    "            # 多 +1 是为了方便求后面用二维前缀和复原\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 4. 直接在 diff 上复原（二维前缀和），计算最大值\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "                ans = max(ans, diff[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        # 1. 统计所有左下和右上坐标\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "        for i, j, side in forceField:\n",
    "            x_set.add(2 * i - side)\n",
    "            x_set.add(2 * i + side)\n",
    "            y_set.add(2 * j - side)\n",
    "            y_set.add(2 * j + side)\n",
    "\n",
    "        # 2. 离散化\n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "        n, m = len(xs), len(ys)\n",
    "\n",
    "        # 3. 二维差分\n",
    "        diff = [[0] * (m + 2) for _ in range(n + 2)]\n",
    "        for i, j, side in forceField:\n",
    "            r1 = bisect_left(xs, 2 * i - side)\n",
    "            r2 = bisect_left(xs, 2 * i + side)\n",
    "            c1 = bisect_left(ys, 2 * j - side)\n",
    "            c2 = bisect_left(ys, 2 * j + side)\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 4. 二维前缀和复原，并计算最大值\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "                ans = max(ans, diff[i][j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        # 1. 统计所有左下和右上坐标\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "        for i, j, side in forceField:\n",
    "            x_set.add(2 * i - side)\n",
    "            x_set.add(2 * i + side)\n",
    "            y_set.add(2 * j - side)\n",
    "            y_set.add(2 * j + side)\n",
    "\n",
    "        # 2. 离散化\n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "        n, m = len(xs), len(ys)\n",
    "\n",
    "        # 3. 二维差分：快速地把一个矩形范围内的数都 +1\n",
    "        diff = [[0] * (m + 2) for _ in range(n + 2)]\n",
    "        for i, j, side in forceField:\n",
    "            r1 = bisect_left(xs, 2 * i - side)\n",
    "            r2 = bisect_left(xs, 2 * i + side)\n",
    "            c1 = bisect_left(ys, 2 * j - side)\n",
    "            c2 = bisect_left(ys, 2 * j + side)\n",
    "            # 将区域 r1<=r<=r2 && c1<=c<=c2 上的数都加上 x\n",
    "            # 多 +1 是为了方便求后面用二维前缀和复原\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 4. 直接在 diff 上复原（二维前缀和），计算最大值\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "                ans = max(ans, diff[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        # 1. 统计所有左下和右上坐标\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "        for i, j, side in forceField:\n",
    "            x_set.add(2 * i - side)\n",
    "            x_set.add(2 * i + side)\n",
    "            y_set.add(2 * j - side)\n",
    "            y_set.add(2 * j + side)\n",
    "\n",
    "        # 2. 离散化\n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "        n, m = len(xs), len(ys)\n",
    "\n",
    "        # 3. 二维差分：快速地把一个矩形范围内的数都 +1\n",
    "        diff = [[0] * (m + 2) for _ in range(n + 2)]\n",
    "        for i, j, side in forceField:\n",
    "            r1 = bisect_left(xs, 2 * i - side)\n",
    "            r2 = bisect_left(xs, 2 * i + side)\n",
    "            c1 = bisect_left(ys, 2 * j - side)\n",
    "            c2 = bisect_left(ys, 2 * j + side)\n",
    "            # 将区域 r1<=r<=r2 && c1<=c<=c2 上的数都加上 x\n",
    "            # 多 +1 是为了方便求后面用二维前缀和复原\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 4. 直接在 diff 上复原（二维前缀和），计算最大值\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "                ans = max(ans, diff[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, a: List[List[int]]) -> int:\n",
    "        xs,ys=set(),set()\n",
    "        for x,y,s in a:\n",
    "            xs.add(x+s/2)\n",
    "            xs.add(x-s/2)\n",
    "            ys.add(y-s/2)\n",
    "            ys.add(y+s/2)\n",
    "        #  xs X ys 的所有点处\n",
    "        #  |     ____|_____\n",
    "        #  |____|____|     |\n",
    "        #       |__________|\n",
    "        #  将 xs 从小到大排序,起点+1,终点-1 (forceField.length <= 100个矩形)\n",
    "        #  对于每个矩形, 计算左边是第几点位,右边是第几点位, 之间的所有点位力场+1\n",
    "        #  对于当前矩形,矩形内部的所有位置都有一层祝福力场\n",
    "        xs=sorted(xs)\n",
    "        ys=sorted(ys)\n",
    "        ans=0\n",
    "        mat=[[0]*len(ys) for _ in range(len(xs))]\n",
    "        for x,y,s in a:\n",
    "            left = bisect_left(xs,x-s/2)\n",
    "            right= bisect_right(xs,x+s/2)\n",
    "            low = bisect_left(ys,y-s/2)\n",
    "            up= bisect_right(ys,y+s/2)\n",
    "            for i in range(left,right):\n",
    "                for j in range(low,up):\n",
    "                    mat[i][j]+=1\n",
    "                    ans=max(ans,mat[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        xs = []\n",
    "        ys = []\n",
    "        cor = []\n",
    "        for f in forceField:\n",
    "            a, b, c, d = self.convert(f)\n",
    "            cor.append([a, b, c, d])\n",
    "            xs.append(a)\n",
    "            xs.append(c)\n",
    "            ys.append(b)\n",
    "            ys.append(d)\n",
    "        x = list(sorted(set(xs)))\n",
    "        y = list(sorted(set(ys)))\n",
    "        xd = {}\n",
    "        yd = {}\n",
    "        for i in range(len(x)):\n",
    "            xd[x[i]] = i\n",
    "        for j in range(len(y)):\n",
    "            yd[y[j]] = j\n",
    "        \n",
    "        m = len(x) + 2\n",
    "        n = len(y) + 2\n",
    "        s = [[0]*n for _ in range(m)]\n",
    "        maxf = 0\n",
    "        for [a,b,c,d] in cor:\n",
    "            s[xd[a]+1][yd[b]+1] += 1\n",
    "            s[xd[c]+2][yd[b]+1] -= 1\n",
    "            s[xd[a]+1][yd[d]+2] -= 1\n",
    "            s[xd[c]+2][yd[d]+2] += 1\n",
    "        for i in range(1, len(s)-1):\n",
    "            for j in range(1, len(s[0])-1):\n",
    "                s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1]\n",
    "                maxf = max(maxf, s[i][j])\n",
    "        return maxf\n",
    "\n",
    "\n",
    "    def convert(self, forceField):\n",
    "        a = forceField[1]*2 - forceField[2]\n",
    "        b = forceField[0]*2 - forceField[2]\n",
    "        c = forceField[1]*2 + forceField[2]\n",
    "        d = forceField[0]*2 + forceField[2]\n",
    "        return a, b, c, d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        xs = []\n",
    "        ys = []\n",
    "        cor = []\n",
    "        for f in forceField:\n",
    "            a, b, c, d = self.convert(f)\n",
    "            cor.append([a, b, c, d])\n",
    "            xs.append(a)\n",
    "            xs.append(c)\n",
    "            ys.append(b)\n",
    "            ys.append(d)\n",
    "        x = list(sorted(set(xs)))\n",
    "        y = list(sorted(set(ys)))\n",
    "        xd = {}\n",
    "        yd = {}\n",
    "        for i in range(len(x)):\n",
    "            xd[x[i]] = i\n",
    "        for j in range(len(y)):\n",
    "            yd[y[j]] = j\n",
    "        \n",
    "        m = len(x) + 2\n",
    "        n = len(y) + 2\n",
    "        s = [[0]*n for _ in range(m)]\n",
    "        maxf = 0\n",
    "        for [a,b,c,d] in cor:\n",
    "            s[xd[a]+1][yd[b]+1] += 1\n",
    "            s[xd[c]+2][yd[b]+1] -= 1\n",
    "            s[xd[a]+1][yd[d]+2] -= 1\n",
    "            s[xd[c]+2][yd[d]+2] += 1\n",
    "        for i in range(1, len(s)-1):\n",
    "            for j in range(1, len(s[0])-1):\n",
    "                s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1]\n",
    "                maxf = max(maxf, s[i][j])\n",
    "        return maxf\n",
    "\n",
    "\n",
    "    def convert(self, forceField):  # 在转换成坐标时，不用管在图上上下是否颠倒，只需要根据给定的中心坐标x，y来确定左上角和右下角的坐标就可以了，图可以自己画\n",
    "        a = forceField[1]*2 - forceField[2]\n",
    "        b = forceField[0]*2 - forceField[2]\n",
    "        c = forceField[1]*2 + forceField[2]\n",
    "        d = forceField[0]*2 + forceField[2]\n",
    "        return a, b, c, d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:\n",
    "        x_set = set()\n",
    "        y_set = set()\n",
    "        for x, y, side in forceField:\n",
    "            x_set.add(x*2 - side)\n",
    "            x_set.add(x*2 + side)\n",
    "            y_set.add(y*2 - side)\n",
    "            y_set.add(y*2 + side)\n",
    "        xs = sorted(x_set)\n",
    "        ys = sorted(y_set)\n",
    "        row, col = len(ys), len(xs)\n",
    "        diff = [[0 for j in range(col + 2)] for i in range(row + 2)]\n",
    "\n",
    "        for x, y, side in forceField:\n",
    "            r1 = bisect_left(ys, y * 2 - side)\n",
    "            c1 = bisect_left(xs, x * 2 - side)\n",
    "            r2 = bisect_left(ys, y * 2 + side)\n",
    "            c2 = bisect_left(xs, x * 2 + side)\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "\n",
    "        force_num = 0\n",
    "        for i in range(1, row + 2):\n",
    "            for j in range(1, col + 2):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "                force_num = max(force_num, diff[i][j])\n",
    "        return force_num"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
